//
//  253_会议室-2.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/16.
/**
 至少需要多少间会议室
 */

import UIKit

/// 使用小顶堆，堆顶存的是最小的会议结束时间
class HuiYiShi2: NSObject {

    func QA() {
        print(HuiYi([[0,6],[4,14],[8,24],[16,22], [20,26]])) // 3
    }
    
    func HuiYi(_ huiArray: [[Int]]) -> Int {
        if huiArray.count < 2 {
            return huiArray.count
        }
        var begins = [Int]()
        var ends = [Int]()
        for item in huiArray {
            begins.append(item[0])
            ends.append(item[1])
        }
        begins.sort()
        ends.sort()
        var room = 0, endIndex = 0
        for begin in begins {
            if begin >= ends[endIndex] { // 不需要再开会议室
                endIndex += 1
            } else { // 需要开会议室
               room += 1
            }
        }
        return room
    }
    
    // 使用小顶堆
    func HuiYi1(_ huiArray: [[Int]]) -> Int {
        if huiArray.count < 2 {
            return huiArray.count
        }
        let heap = BinaryHeap(defaultValue: -1, .mix_binary_heap)
        heap.add(huiArray[0][1]) // 将第一个会议室结束时间放到小顶堆中
        for i in 1..<huiArray.count  {
            let hui = huiArray[i]
            let min = heap.get() ?? Int.max
            // 需要释放一个会议室，将自己的结束时间加进去
            if hui[0] >= min {
                heap.remove()
                heap.add(hui[1])
            } else { // 需要新开一个会议室
                heap.add(hui[1])
            }
        }
        return heap.size()
    }
}
